// 给定一个链表的头节点head，链表中每个节点除了next指针之外，还包含一个随机指针random，该指针可以指向链表中的任何节点或者空节点
// 要求将该链表进行深拷贝，返回复制链表的头节点

// 思路：两次遍历链表，第一次将旧节点和新节点用map映射，第二次遍历，更新新节点指针指向的节点
// 时间复杂度：O(n)
// 空间复杂度：O(n)

function copyRandomList(head) {
    const map = new Map
    let cur = head
    while (cur) {
        map.set(cur, new _Node(cur.val, null, null))
        cur = cur.next
    }
    cur = head
    while (cur) {
        if (map.has(cur.next)) {
            map.get(cur).next = map.get(cur.next)
        }
        if (map.has(cur.random)) {
            map.get(cur).random = map.get(cur.random)
        }
        cur = cur.next
    }
    return map.get(head)
}

function _Node(val, next, random) {
   this.val = val;
   this.next = next;
   this.random = random;
};